package done.normal_301_400;

import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 377. Combination Sum IV 组合总和 Ⅳ
 * <p>
 * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
 * <p>
 * 示例:  nums = [1, 2, 3]    target = 4
 * <p>
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * <p>
 * 请注意，顺序不同的序列被视作不同的组合。因此输出为 7。
 * <p>
 * 2019-05-19 12:33
 **/
@SuppressWarnings("all")
public class CombinationSumIV {

    // 动态规划
    public int combinationSum4(int[] nums, int target) {
        // 190520 first
        return -1;
    }

    @Test
    public void test() {
        info(combinationSum4(new int[]{1, 2, 3}, 4));
    }
}





























/*
// 1. 递归
public int combinationSum4(int[] nums, int target) {
    if (target == 0) {
        return 1;
    }
    int res = 0;
    for (int num : nums) {
        if (target >= num) {
            res += combinationSum4(nums, target - num);
        }
    }
    return res;
}

// 2. 动态规划
public int combinationSum4(int[] nums, int target) {
    int[] memo = new int[target + 1];
    memo[0] = 1;
    for (int i = 0; i < target; i++) {
        for (int num : nums) {
            if (i + num <= target)
                memo[i + num] += memo[i];
        }
    }
    return memo[target];
}
*/
